#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: dijkstra.py 
@version:
@time: 2024/01/14 
"""
import sys

MAX = sys.maxsize
graph1 = [
    [0, 4, MAX, 2, MAX],
    [41, 0, 4, 1, MAX],
    [MAX, 40, 0, 1, 3],
    [2, 1, 1, 0, 7],
    [MAX, MAX, 32, 7, 0]
]
point1 = ['A', 'B', 'C', 'D', 'E']
start1 = 0


def dijkstra(graph, point, start):
    length = graph[start]
    use = [0 for _ in range(len(graph))]
    use[start] = 1
    front = [point[start] for _ in range(len(graph))]
    for i in range(len(graph)):
        minid = 0
        min_index = sys.maxsize
        for j in range(len(length)):
            if not use[j] and length[j] < min_index:
                min_index = length[j]
                minid = j
        use[minid] = 1
        for k in range(len(graph)):
            if not use[k] and min_index + graph[minid][k] < length[k]:
                length[k] = min_index + graph[minid][k]
                front[k] = point[minid]
    return length, front


result = dijkstra(
    graph1,
    point1,
    start1
)

print(result)
